#include <stdio.h>
#include <stdlib.h>
#include <png.h>
#include <pngconf.h>
#include <string.h>
#include <io.h>

#define TEX_PNG "spritetex.png"
#define TEX_CPP "spritetex.cpp"
#define TEX_H   "spritetex.h"

#define MAX(x, y) (((x) < (y)) ? (y) : (x))
#define MIN(x, y) (((x) > (y)) ? (y) : (x))

typedef struct {
	unsigned int x;
	unsigned int y;
	unsigned int length;
} square;

typedef struct {
	png_uint_32	width;
	png_uint_32	height;
	png_bytep *rows;
	unsigned int max;
	unsigned int min;
	unsigned char *buffer;
	unsigned int x;
	unsigned int y;
	unsigned int rotated;
	char texname[1024];
} image;

void copy_image(image *out, image *in) {
	if (!in->rotated) {
		for(unsigned int i = 0; i < in->height; i++)
			memcpy(out->rows[in->y + i] + (in->x * 4), in->rows[i], in->width * 4);
		return;
	}

	for(unsigned int j = 0; j < in->width; j++) {
		for(unsigned int i = 0; i < in->height; i++) {
			out->rows[in->y + j][(in->x + i) * 4 + 0] = in->rows[i][j * 4 + 0];
			out->rows[in->y + j][(in->x + i) * 4 + 1] = in->rows[i][j * 4 + 1];
			out->rows[in->y + j][(in->x + i) * 4 + 2] = in->rows[i][j * 4 + 2];
			out->rows[in->y + j][(in->x + i) * 4 + 3] = in->rows[i][j * 4 + 3];
		}
	}
}

int create_buffer(image *out, unsigned int length, int count, image *img) {
	out->width = length;
	out->height = length;
	out->buffer = (unsigned char *)malloc(length * length * 4);

	if (out->buffer == NULL)
		return 1;

	out->rows = new png_bytep[out->height];
	if (out->rows == NULL) {
		free(out->buffer);
		return 2;
	}

	memset(out->buffer, 0x00, length * length * 4);

	for (unsigned int i = 0; i < out->height; i++)
		out->rows[i] = out->buffer + length * i * 4;

	for (int i = 0; i < count; i++)
		copy_image(out, img + i);

	return 0;		
}

int save_png(unsigned int length, int count, image *img) {
	image out;
	
	if (create_buffer(&out, length, count, img))
		return 1;

	mkdir("sprites");
	mkdir("sprites/textures");

	FILE *fp = fopen("sprites/textures/" TEX_PNG, "wb");
	if (fp == NULL)
		return 2;

	png_structp png = png_create_write_struct(PNG_LIBPNG_VER_STRING, (png_voidp)NULL, NULL, NULL);
	if (!png) {
		fclose(fp);
		free(out.buffer);
		delete [] out.rows;
		return 3;
	}

	png_infop info = png_create_info_struct(png);
	if (!info) {
		fclose(fp);
		free(out.buffer);
		delete [] out.rows;
		png_destroy_read_struct(&png, (png_infopp)NULL, (png_infopp)NULL);
		return 4;
	}

	if (setjmp(png_jmpbuf(png))) {
		png_destroy_read_struct(&png, &info, NULL);
		fclose(fp);
		free(out.buffer);
		delete [] out.rows;
		return 5;
	}

	png_init_io(png, fp);
	png_set_IHDR(png, info, out.width, out.height, 8, PNG_COLOR_TYPE_RGB_ALPHA, PNG_INTERLACE_NONE, PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);
	png_set_rows(png, info, out.rows);
	png_write_png(png, info, PNG_TRANSFORM_IDENTITY, NULL);
	png_destroy_write_struct(&png, &info);
	
	return 0;
}

int load_png(const char* filename, image *img) {
	if (filename == NULL)
		return 0;

	FILE *fp = fopen(filename, "rb");
	if (!fp) {
		printf("1\n");
		return 0;
	}

	png_structp png = png_create_read_struct(PNG_LIBPNG_VER_STRING, (png_voidp)NULL, NULL, NULL);
	if (!png) {
		fclose(fp);
		printf("2\n");
		return 0;
	}

	png_infop info = png_create_info_struct(png);
	if (!info) {
		fclose(fp);
		png_destroy_read_struct(&png, (png_infopp)NULL, (png_infopp)NULL);
		printf("3\n");
		return 0;
	}

	if (setjmp(png_jmpbuf(png))) {
		png_destroy_read_struct(&png, &info, NULL);
		fclose(fp);
		printf("4\n");
		return 0;
	}

	png_init_io(png, fp);

	png_read_info(png, info);

	int bit_depth;
	int color_type;
	int interlace_type;
	int compression_type;
	int filter_method;

	png_get_IHDR(png, info, &img->width, &img->height, &bit_depth, &color_type, &interlace_type, &compression_type, &filter_method);

	if (color_type == PNG_COLOR_TYPE_PALETTE)
		png_set_palette_to_rgb(png);
	if (color_type == PNG_COLOR_TYPE_GRAY && bit_depth < 8)
		png_set_gray_1_2_4_to_8(png);
	if (png_get_valid(png, info, PNG_INFO_tRNS))
		png_set_tRNS_to_alpha(png);
	if (bit_depth < 8)
		png_set_packing(png);
	if (bit_depth == 16)
		png_set_strip_16(png);
	if (color_type == PNG_COLOR_TYPE_GRAY || color_type == PNG_COLOR_TYPE_GRAY_ALPHA)
		png_set_gray_to_rgb(png);
	png_set_filler(png, 0xffff, PNG_FILLER_AFTER);
	
	png_read_update_info(png, info);	

	png_get_IHDR(png, info, &img->width, &img->height, &bit_depth, &color_type, &interlace_type, &compression_type, &filter_method);

	unsigned int bytes_per_row = png_get_rowbytes(png, info);
	unsigned int bytes_per_pixel = bytes_per_row / (img->width);
	
	if ((color_type != PNG_COLOR_TYPE_RGB) && (color_type != PNG_COLOR_TYPE_RGB_ALPHA) && (bytes_per_pixel != 4)) {
		printf("5\n");
		fclose(fp);
		png_destroy_read_struct(&png, &info, NULL);
		return 0;
	}

	img->buffer = (unsigned char *) malloc(bytes_per_row * (img->height));
	if (img->buffer == NULL) {
		printf("6\n");
		fclose(fp);
		png_destroy_read_struct(&png, &info, NULL);
		return 0;
	}

	img->rows = new png_bytep[img->height];
	if (img->rows == NULL) {
		printf("7\n");
		fclose(fp);
		free(img->buffer);
		png_destroy_read_struct(&png, &info, NULL);
		return 0;
	}

	for (unsigned int i = 0; i < img->height; i++)
		img->rows[i] = img->buffer + bytes_per_row * i;

	png_read_image(png, img->rows);

	png_read_end(png, NULL);
	png_destroy_read_struct(&png, &info, NULL);

	return 1;
}

int test_power(unsigned int n) {
	for(unsigned int i = 0; i < 32; i++) {
		if (n == (1u << i))
			return 1;
	}
	return 0;
}

int test_size(image *img) {
	if (!test_power(img->width))
		return 0;
	if (!test_power(img->height))
		return 0;

	img->max = MAX(img->width, img->height);
	img->min = MIN(img->width, img->height);

	if (img->height == img->width)
		return 1;

	if ((img->max / img->min) == 2)
		return 1;
	return 0;
}

int parse_line(char *line, char **filename, char **tex_name) {
	if (line == NULL)
		return 0;
	
	int length = strlen(line);
	if (length == 0)
		return 0;
		
	if (line[length - 1] == '\n')
		line[length - 1] = '\0';

	if (length == 1)
		return 0;
		
	if (line[length - 2] == '\r')
		line[length - 2] = '\0';

	*filename = strtok(line, " \t\r\n");
	if (*filename == NULL)
		return 0;
	
	*tex_name = strtok(NULL, " \t\r\n");
	if (*tex_name == NULL)
		return 0;
	
	return 1;
}

int test_point(unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, unsigned int w2, unsigned int h2) {
	return (x1 >= x2) && (x1 < (x2 + w2)) && (y1 >= y2) && (y1 < (y2 + h2));
}

int intersect(unsigned int x1, unsigned int y1, unsigned int w1, unsigned int h1, unsigned int x2, unsigned int y2, unsigned int w2, unsigned int h2) {
	if (test_point(x1, y1, x2, y2, w2, h2))
		return 1;
	if (test_point(x1 + w1 - 1, y1, x2, y2, w2, h2))
		return 1;
	if (test_point(x1 + w1 - 1, y1 + h1 - 1, x2, y2, w2, h2))
		return 1;
	if (test_point(x1, y1 + h1 - 1, x2, y2, w2, h2))
		return 1;

	if (test_point(x2, y2, x1, y1, w1, h1))
		return 1;
	if (test_point(x2 + w2 - 1, y2, x1, y1, w1, h1))
		return 1;
	if (test_point(x2 + w2 - 1, y2 + h2 - 1, x1, y1, w1, h1))
		return 1;
	if (test_point(x2, y2 + h2 - 1, x1, y1, w1, h1))
		return 1;

	return 0;
}

int valid_pos(square *s, int start, int current, image *img, unsigned int x, unsigned int y) {
	if ((x < s->x) || (y < s->y) || ((x + img[current].max) > (s->x + s->length)) || ((y + img[current].min) > (s->y + s->length)))
		return 0;
	
	for (int i = start; i < current; i++) {
		if (intersect(img[i].x, img[i].y, img[i].max, img[i].min, x, y, img[current].max, img[current].min))
			return 0;
	}
	
	return 1;
}

int choose_pos(square *s, int start, int current, image *img) {
	unsigned int min_x = s->x + s->length;
	unsigned int min_y = s->y + s->length;

	unsigned int x, y;
	
	x = s->x;
	y = s->y;
	if (valid_pos(s, start, current, img, x, y)) {
		if ((x < min_x) || ((x == min_x) && (y < min_y))) {
			min_x = x;
			min_y = y;
		}
	}

	for(int i = start; i < current; i++) {
		x = img[i].x + ((img[i].rotated) ? (img[i].height) : (img[i].width));
		y = img[i].y;
		if (valid_pos(s, start, current, img, x, y)) {
			if ((x < min_x) || ((x == min_x) && (y < min_y))) {
				min_x = x;
				min_y = y;
			}
		}
	}

	for(int i = start; i < current; i++) {
		x = img[i].x;
		y = img[i].y + ((img[i].rotated) ? (img[i].width) : (img[i].height));
		if (valid_pos(s, start, current, img, x, y)) {
			if ((x < min_x) || ((x == min_x) && (y < min_y))) {
				min_x = x;
				min_y = y;
			}
		}
	}
	
	if ((min_x == s->x + s->length) || (min_y == s->y + s->length))
		return 0;
	
	img[current].rotated = 0;
	if (img[current].max > img[current].width)
		img[current].rotated = 1;

	img[current].x = min_x;
	img[current].y = min_y;
	
	return 1;
}

int pack_into_square(square *s, int start, int count, image *img) {
	int current = start;
	
	while (current < count) {
		if (!choose_pos(s, start, current, img))
			break;
		current++;
	}
	return current;
}

int pack_square_sides(square *top, int current, int count, image *img) {
	unsigned int length = top->length;
	unsigned int current_expansion = img[current].min;

	top->length += current_expansion;

	unsigned int num = length / img[current].min;

	square temp;
	
	temp.length = current_expansion;

	// First column
	temp.x = top->x + length;
	for(unsigned int i = 0; i < num; i++) {
		temp.y = top->y + i * temp.length;
		
		if (img[current].max > current_expansion) {
			img[current].x = temp.x;
			img[current].y = temp.y;
			img[current].rotated = 0;
			if (img[current].max > img[current].height)
				img[current].rotated = 1;
			current++;
			i++;
		} else {
			current = pack_into_square(&temp, current, count, img);
		}
		if (current >= count)
			return current;
	}
	
	// First row
	temp.y = top->y + length;
	for(unsigned int i = 0; i < num; i++) {
		temp.x = top->x + i * temp.length;

		if (img[current].max > current_expansion) {
			img[current].x = temp.x;
			img[current].y = temp.y;
			img[current].rotated = 0;
			if (img[current].max > img[current].width)
				img[current].rotated = 1;
			current++;
			i++;
		} else {
			current = pack_into_square(&temp, current, count, img);
		}
		if (current >= count)
			return current;
	}

	temp.x = top->x + num * temp.length;

	// If there are no more rectangles, just fill the last square and return
	if (img[current].max <= current_expansion)
		return pack_into_square(&temp, current, count, img);

	top->length += current_expansion;

	// This piece is always in a different position
	img[current].x = temp.x;
	img[current].y = temp.y;
	img[current].rotated = 0;
	if (img[current].max > img[current].width)
		img[current].rotated = 1;
	current++;
	if (current >= count)
		return current;

	// Second column
	temp.x = top->x + length + current_expansion;
	for(unsigned int i = 0; i < num; i++) {
		temp.y = top->y + i * temp.length;
		
		if (img[current].max > current_expansion) {
			img[current].x = temp.x;
			img[current].y = temp.y;
			img[current].rotated = 0;
			if (img[current].max > img[current].height)
				img[current].rotated = 1;
			current++;
			i++;
		} else {
			current = pack_into_square(&temp, current, count, img);
		}
		if (current >= count)
			return current;
	}

	// Second row (this one is longer than the first one)
	temp.y = top->y + length + current_expansion;
	for(unsigned int i = 0; i < (num + 2); i++) {
		temp.x = top->x + i * temp.length;

		if (img[current].max > current_expansion) {
			img[current].x = temp.x;
			img[current].y = temp.y;
			img[current].rotated = 0;
			if (img[current].max > img[current].width)
				img[current].rotated = 1;
			current++;
			i++;
		} else {
			current = pack_into_square(&temp, current, count, img);
		}
		if (current >= count)
			return current;
	}

	return current;
}

void pack(square *top, int current, int count, image *img) {
	if (count == 0)
		return;
		
	if (top->length == 0) {
		top->length = img[current].max;
		current = pack_into_square(top, current, count, img);
	}
	
	while (current < count) {
		current = pack_square_sides(top, current, count, img);
	}
}

void calculate_coords(double coords[4][2], unsigned int x, unsigned int y, unsigned int w, unsigned int h, int rotated, double length) {
	if (rotated) {
		unsigned int temp = w;
		w = h;
		h = temp;
	}

	coords[0][0] = ((double)x) / length;
	coords[0][1] = ((double)y) / length;

	if (rotated) {
		coords[1][0] = ((double)(x + w)) / length;
		coords[1][1] = ((double)(y)) / length;
	} else {
		coords[1][0] = ((double)(x)) / length;
		coords[1][1] = ((double)(y + h)) / length;
	}

	coords[2][0] = ((double)(x + w)) / length;
	coords[2][1] = ((double)(y + h)) / length;

	if (rotated) {
		coords[3][0] = ((double)(x)) / length;
		coords[3][1] = ((double)(y + h)) / length;
	} else {
		coords[3][0] = ((double)(x + w)) / length;
		coords[3][1] = ((double)(y)) / length;
	}
}

int save_cpp(unsigned int length, int count, image *img) {
	mkdir("sprites");

	FILE *fp = fopen("sprites/" TEX_H, "w");
	if (fp == NULL)
		return 1;
	
	fprintf(fp, "#ifndef __SPRITETEX_H\n");
	fprintf(fp, "#define __SPRITETEX_H\n");
	fprintf(fp, "\n");

	fprintf(fp, "#define NUM_SPRITES %d\n", count);

	fprintf(fp, "\n");

	for(int i = 0; i < count; i++)
		fprintf(fp, "#define %s %d\n", img[i].texname, i);

	fprintf(fp, "\n");

	fprintf(fp, "typedef struct {\n");
	fprintf(fp, "  double x1, y1;\n");
	fprintf(fp, "  double x2, y2;\n");
	fprintf(fp, "  double x3, y3;\n");
	fprintf(fp, "  double x4, y4;\n");
	fprintf(fp, "} TEX_COORD;\n");

	fprintf(fp, "\n");

	fprintf(fp, "extern TEX_COORD tex_coord[%d];\n", count);

	fprintf(fp, "\n");

	fprintf(fp, "#endif\n");
	
	fclose(fp);
	
	fp = fopen("sprites/" TEX_CPP, "w");
	if (fp == NULL)
		return 1;
	
	fprintf(fp, "#include \"" TEX_H "\"\n");
	fprintf(fp, "\n");

	fprintf(fp, "TEX_COORD tex_coord[%d] = {\n", count);

	for(int i = 0; i < count; i++) {
		double coords[4][2];

		calculate_coords(coords, img[i].x, img[i].y, img[i].width, img[i].height, img[i].rotated, (double)length);

		fprintf(fp, "  { %f, %f, %f, %f, %f, %f, %f, %f },\n",
			coords[0][0], coords[0][1], coords[1][0], coords[1][1],
			coords[2][0], coords[2][1], coords[3][0], coords[3][1]);
	}

	fprintf(fp, "};\n");

	fprintf(fp, "\n");
	
	fclose(fp);
	
	return 0;
}

int qsort_compare(const void *e1, const void *e2) {
	image *i1 = (image *)e1;
	image *i2 = (image *)e2;

	if (i1->max > i2->max)
		return -1;
	if (i1->max < i2->max)
		return 1;
	if (i1->min > i2->min)
		return -1;
	if (i1->min < i2->min)
		return 1;
	return 0;
}

image img[1024];

int main(int argc, const char* argv[]) {
	char line[1024];

	if (argc != 2) {
		printf ("Usage: %s <definition_file>\n", argv[0]);
		return 1;
	}

	FILE *def = fopen(argv[1], "r");
	if (def == NULL) {
		printf ("Can't open definition file %s\n", argv[1]);
		return 2;
	}

	int count = 0;
	int line_count = 0;
	
	printf("Loading definition file...\n");

	while (fgets(line, 1024, def) != NULL) {
		line_count++;
		
		char *filename;
		char *tex_name;
		
		if (!parse_line(line, &filename, &tex_name)) {
			printf("Error parsing line %d: '%s'\n", line_count, line);
			continue;
		}
		
		if (!load_png(filename, &img[count])) {
			printf("Error loading texture '%s' at line %d\n", filename, line_count);
			continue;
		}

		if (!test_size(&img[count])) {
			printf("Error using texture '%s' at line %d: lengths must be a power of 2 and have 1:1 or 1:2 proportions\n", filename, line_count);
			continue;
		}
			
		strcpy(img[count].texname, tex_name);

		unsigned int half_width = (unsigned int)img[count].width / 2;
		unsigned int half_height = (unsigned int)img[count].height / 2;

		printf("w = %3u, h = %3u, sample = %02x %02x %02x %02x, file = %s\n", 
					(unsigned int)img[count].width, 
					(unsigned int)img[count].height, 
					img[count].rows[half_height][half_width * 4 + 0], 
					img[count].rows[half_height][half_width * 4 + 1], 
					img[count].rows[half_height][half_width * 4 + 2], 
					img[count].rows[half_height][half_width * 4 + 3], 
					filename);

		count++;
	}
	
	if (count == 0) {
		printf("No permited images found\n");
		exit(0);
	}

	printf("Sorting images...");
	qsort(img, count, sizeof(image), qsort_compare);
	printf(" ok\n");

	square top;
	
	top.x = top.y = top.length = 0;
	
	printf("Packing images...");
	pack(&top, 0, count, img);
	printf(" ok\n");

	printf("Packed info:\nFinal size: %u\n", top.length);
	for (int i = 0; i < count; i++)
		if (img[i].rotated)
			printf("(%u, %u | %u, %u) '%s'\n", img[i].x, img[i].y, (unsigned int)img[i].height, (unsigned int)img[i].width, img[i].texname);
		else
			printf("(%u, %u | %u, %u) '%s'\n", img[i].x, img[i].y, (unsigned int)img[i].width, (unsigned int)img[i].height, img[i].texname);

	printf("\nSaving final texture at '" TEX_PNG "'...");
	if (save_png(top.length, count, img))
		printf(" error\n\n");
	else
		printf(" ok\n");

	printf("Generating C++ output...");
	if (save_cpp(top.length, count, img))
		printf(" error\n\n");
	else
		printf(" ok\n");
}
